Among the primary objectives of a digital data compression system are the removal of redundant information and the accurate representation of remaining information using a minimum number of bits, before the data is conveyed via a transmission channel or storage medium. Data to be compressed may represent various types of information, such as audio and video information for example.
Coding of data for compression often requires that two factors be considered in particular, namely, the location of significant data and the value of significant non-zero data. Compression coding of data locations, which may be represented by the entries of a so-called significance map, advantageously augments the coding of the significant non-zero data.
Recent developments in the field of image signal processing, among others, continue to focus attention on a need for efficient and accurate forms of data compression coding. In this regard various forms of so-called "pyramid" signal processing have been proposed, particularly in the context of image information processing. Multiresolution "pyramid" processing of image data is described, for example, by Burt et al. in "The Laplacian Pyramid as a Compact Image Code", IEEE Transactions on Communications, Vol. Com-31, No. 4, April 1983. A so-called "wavelet" pyramid is a specific type of multiresolution pyramid that uses quadrature mirror filters (QMF) to produce subband decompositions of an original image representative video signal. A signal processor of this type is described by Pentland et al. in "A Practical Approach to Fractal-Based Image Compression", Proceedings of the DCC '91 Data Compression Conference, Apr. 8-11, 1991, IEEE Computer Society Press, Los Alamitos, Calif. The Pentland et al. compression system attempts to use low frequency coarse scale information to predict significant information at high frequency finer scales. QMF subband pyramid processing also is described in the book "Subband Image Coding", J. W. Woods, ed., Kluwer Academic Publishers, 1991.
Another system for pyramid processing image data is described by Lewis et al. in "A 64 Kb/s Video Codec Using the 2-D Wavelet Transform", Proceedings of the DCC '91 Data Compression Conference as mentioned above. Lewis et al. describe a coding system based on a model of human visual perception. Decomposed high pass bands are coded by constructing spatially local trees having nodes comprising 2.times.2 blocks of subtrees. The energy (a statistical measure) of a tree is compared with a human visual system weighted threshold to determine if a tree is important or not. If not, the coder assumes that the remainder of the tree if zero and a "zero flag" is sent.
A disclosed system according to the present invention uses the absence of significant low frequency coarse scale information to predict the absence of significant information at higher frequency finer scales, in contrast to the Pentland et al. system which conversely attempts to predict significant information. In addition, the disclosed system advantageously does not rely upon a statistical measure, such as energy, associated with a block of plural coefficients as in Lewis et al., since such reliance may lead to a significant coefficient being obscured by surrounding insignificant coefficients. Also unlike Lewis et al., a system according to the present invention guarantees that for a given threshold neither a root element of a tree structure nor any descendant of a root element has a magnitude greater than the threshold. The disclosed system can accurately and unambiguously determine and represent, with a single symbol, a series of individual coefficients which are insignificant with respect to a given threshold, thereby defining a tree structure (i.e., a zerotree) based upon an evaluation of individual coefficients.